Little trick--字符串包含

题目描述

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？

为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)

比如，如果是下面两个字符串：

String 1：ABCD

String 2：BAD

答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。

如果是下面两个字符串：

String 1：ABCD

String 2：BCE

答案是false，因为字符串String2里的E字母不在字符串String1里。

同时，如果string1：ABCD，string 2：AA，同样返回true。

分析与解法

题目描述虽长，但题意很明了，就是给定一长一短的两个字符串A，B，假设A长B短，要求判断B是否包含在字符串A中。

初看似乎简单，但实现起来并不轻松，且如果面试官步步紧逼，一个一个否决你能想到的方法，要你给出更好、最好的方案时，恐怕就要伤不少脑筋了。

解法一

判断string2中的字符是否在string1中?最直观也是最简单的思路是，针对string2中每一个字符，逐个与string1中每个字符比较，看它是否在String1中。

代码可如下编写：

public static boolean stringContain(String S1,String S2){      
    char[] S1Array=S1.toCharArray();
    char[] S2Array=S2.toCharArray();        
    for(int i=0;i<S2Array.length;i++){
        int j;
        for ( j=0;j<S1Array.length;j++){
            if(S2Array[i]==S1Array[j]){
                break;
            }
        }
        //如果内圈循环结束，判断是否遍历完了还是没有找到相等的
        if (j>=S1Array.length){
            return false;
        }
    }
    return true;
}

假设n是字符串String1的长度，m是字符串String2的长度，那么此算法，需要O(n*m)次操作。显然，时间开销太大，应该找到一种更好的办法。

解法二

如果允许排序的话，我们可以考虑下排序。比如可先对这两个字符串的字母进行排序，然后再同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。

关于排序方法，可采用最常用的快速排序，参考代码如下：


//Version 2 排序后，使用连个指针指向长短两个string，进行遍历
public static boolean stringContain2(String longstr, String shortstr){
    char[] longstrArray=longstr.toCharArray();
    char[] shortstrArray=shortstr.toCharArray();
    Arrays.sort(longstrArray);
    Arrays.sort(shortstrArray);
    int i=0;//point to longstr
    int j=0;//point ot shortstr
    while(j<shortstrArray.length){
        while(i<longstrArray.length&&shortstrArray[j]>longstrArray[i])
            i++;
        if(i>=longstrArray.length){
            return false;
        }
        j++;
    }
    return true;
}

解法三(tricky)

有没有比快速排序更好的方法呢？

我们换一种角度思考本问题：

假设有一个仅由字母组成字串，让每个字母与一个素数对应，从2开始，往后类推，A对应2，B对应3，C对应5，......。遍历第一个字串，把每个字母对应素数相乘。最终会得到一个整数。

利用上面字母和素数的对应关系，对应第二个字符串中的字母，然后轮询，用每个字母对应的素数除前面得到的整数。如果结果有余数，说明结果为false。如果整个过程中没有余数，则说明第二个字符串是第一个的子集了（判断是不是真子集，可以比较两个字符串对应的素数乘积，若相等则不是真子集）。

思路总结如下：

按照从小到大的顺序，用26个素数分别与字符'A'到'Z'一一对应。
遍历长字符串，求得每个字符对应素数的乘积。
遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。
输出结果。如前所述，算法的时间复杂度为O(m+n)的最好的情况为O(n)（遍历短的字符串的第一个数，与长字符串素数的乘积相除，即出现余数，便可退出程序，返回false），n为长字串的长度，空间复杂度为O(1)。由于这个方法太过机智，没有用java去实现，只是照搬了[1]中的C++代码.

//此方法只有理论意义，因为整数乘积很大，有溢出风险。
bool StringContain(string &a,string &b)
{
    const int p[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79, 83, 89, 97, 101};
    int f = 1;
    for (int i = 0; i < a.length(); ++i)
    {
        int x = p[a[i] - 'A'];
        if (f % x)
        {
            f *= x;
        }
    }
    for (int i = 0; i < b.length(); ++i)
    {
        int x = p[b[i] - 'A'];
        if (f % x)
        {
            return false;
        }
    }
    return true;
}

解法四(very tricky)

如果面试官继续追问，还有没有更好的办法呢？计数排序？除了计数排序呢？

事实上，可以先把长字符串a中的所有字符都放入一个Hashtable里，然后轮询短字符串b，看短字符串b的每个字符是否都在Hashtable里，如果都存在，说明长字符串a包含短字符串b，否则，说明不包含。

再进一步，我们可以对字符串A，用位运算（26bit整数表示)计算出一个“签名”，再用B中的字符到A里面进行查找。

 
//version 3 “最好的方法”，时间复杂度O(n + m)，空间复杂度O(1)
public static boolean stringContain3(String longstr, String shortstr){
    char[] longstrArray=longstr.toCharArray();
    char[] shortstrArray=shortstr.toCharArray();
    int hash = 0;
    for(int i=0;i<longstrArray.length;i++){
        hash=hash|(1<<(longstrArray[i]-'A'));
    }
    for(int j=0;j<shortstrArray.length;j++){
        if((hash & 1<<(shortstrArray[j]-'A'))==0){
            return false;
        }               
    }
    return true;
}

该方法将字符串转换成为二进制的位值表示，比如“ABCD”，通过第一个循环转换，按位或完之后成了0x0F,二进制表示的话是00001111，再用按位与的方式判断值是否为0，来进行判断是否存在，非常巧妙！这个方法的实质是用一个整数代替了hashtable，空间复杂度为O(1)，时间复杂度还是O(n + m)